#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
int partition(vector<int> &array, int left, int right){
    int rIdx = left + rand() % (right - left + 1);
    swap(array[rIdx], array[left]);
    int pivot = array[left];
    int lt = left;
    for(int idx = left + 1; idx <= right; ++idx){
        if(array[idx] < pivot){
            ++lt;
            swap(array[idx], array[lt]);
        }
    }
    swap(array[lt], array[left]);
    return lt;
}

int partition_I(vector<int> &array, int left, int right){
    int rIdx = left + rand() % (right - left + 1);
    int pivot = array[rIdx];
    swap(array[left], array[rIdx]);
    int lt = left + 1, gt = right;
    while(lt <= gt){
        while(lt <= gt && array[lt] < pivot){
            ++lt;
        }
        while(lt <= gt && array[gt] > pivot){
            --gt;
        }
        if(lt > gt){
            break;
        }
        swap(array[lt], array[gt]);
        ++lt;
        --gt;
    }
    swap(array[gt], array[left]);
    return gt;
}

pair<int,int> partition_II(vector<int> &array, int left, int right){
    int rIdx = left + rand() % (right - left + 1);
    int pivot = array[rIdx];
    swap(array[rIdx], array[left]);
    int lt = left, gt = right + 1;
    for(int idx = left + 1; idx < gt;){
        if(array[idx] < pivot){
            ++lt;
            swap(array[lt], array[idx]);
            ++idx;
        }
        else if(array[idx] > pivot){
            //gt交换过来的数仍然需要比较，故idx不自增
            --gt;
            swap(array[gt], array[idx]);
        }
        else{
            ++idx;
        }
    }
    swap(array[left], array[lt]);
    return {lt - 1, gt};
}

void checkSort(const vector<int> &array){
    int pre;
    for(int idx = 1; idx < array.size(); ++idx){
        pre = array[idx - 1];
        if(array[idx] < pre){
            cout<<"sortError"<<endl;
            return;
        }
    }
    cout<<"sortSuccess"<<endl;
}

void quickSort(vector<int> &array, int left, int right, int mode){
    if(left >= right){
        return;
    }
    switch (mode){
        case 0:{
            int mid = partition(array, left, right);
            quickSort(array, left, mid - 1, mode);
            quickSort(array, mid + 1, right, mode);
            break;
        }
        case 1:{
            int mid = partition_I(array, left, right);
            quickSort(array, left, mid - 1, mode);
            quickSort(array, mid + 1, right, mode);
            break;
        }
        case 2:{
            pair<int,int> p = partition_II(array, left, right);
            quickSort(array, left, p.first, mode);
            quickSort(array, p.second, right, mode);
        }
    }
}

void print(const vector<int> &array){
    cout<<endl;
    for(auto num : array){
        cout<<num<<" ";
    }
    cout<<endl;
}

vector<int> produce(){
    vector<int> product;
    srand(int (time(nullptr)));
    int len = rand() % 500;
    while(len >= 0){
        product.push_back(rand() % 200);
        --len;
    }
    return product;
}
int main(){
    vector<int> tst = produce();
    quickSort(tst, 0, tst.size() - 1, 0);
    print(tst);
    checkSort(tst);
    return 0;
}